/**
 * 递归
 * 很多时候要对一个树状或者网状结构就行查找或者遍历时，往往结构中的深度或
 * 广度不可预测。这时候就需要一个非常重要的算法--递归。
 * 递归在很多时候是非常常见，其算法实现起来非常简约，但是往往并不简单。
 * 一个递归算法要设计两个方面的基本要素：迭代，边界。
 * 比如说要从1+....100.+.n，如果采用递归算法可以这么写
 * javascript代码：
 * var sum = 0;
 * function f(n){
 *      var i = 1;
 *      if(i>n)
 *          return;
 *      sum = i + sum;
 *      f(i+1);
 * }
 * c代码：
 * int f(n){
 *      if(n<1)
 *          return 0;
 *      return n+f(n-1);
 * }
 * 上面的两种风格的递归实现其实代表着两中语言的差异，对于js来说由于存在闭包特性
 * 因此n不会在迭代中消失，而c语言以及c类似的语言中不能这样实现。
 * 迭代是递归的核心，如何让代码按照需求执行下去，肯定需要改变某些参数，要是一直都
 * 一样那就是死循环了。对于js风格的代码，f(i+1)是迭代，i+1就是这迭代中要变的参数。
 * 边界：边界同样非常重要，这函数总不能一直这么执行下去，调用栈会越来越深，直至系统
 * 没有可用的内存空间而崩溃。所以设计递归函数一定要知道什么时候要终止迭代。对于js
 * 代码调用的边界就是n，对于c代码调用的边界就是1。
 * 同步函数和异步函数
 * 这里为什么要提同步函数和异步函数呢？他们之间有什么区别？
 * 同步函数就是函数体执行时按照时间先后顺序执行的，不会发生函数直接的干涉问题。而异步
 * 函数其执行开始和结束的时间是不确定的，那它就会对别的函数参数影响。
 * 比如说有个用户表和一个文章表，文章表中有个指向用户表用户ID的外键。
 * 现在给你个任务，查找某个人名下所有的文章，显然人名不唯一：
 * 实现方法如下：
 * （1）查找人名对应的ID列表
 * （2）根据每个ID查文章表
 * 如果采用同步函数，显然可以很方便实现这个目标：
 * ids = queryUserByName()
 * for(id in ids){
 *      queryArticlesByUserId(id);
 * }
 * 但是对于异步函数来说，query*函数都是立即返回的，你需要给query*传递一个回调函数
 * 才能知道什么时候函数调用结束，才能开始进行下一步。
 * 对于js中由于采用的是单线程，所以为提高效率大量实现异步调用提高效率。但这样往往会
 * 陷入回调陷阱（使用promise可以降低代码复杂性），就是一层层的回调导致代码变得异常
 * 复杂。对于递归来说这显然不是个好消息。
 *
 * 如果在js是使用递归而且函数中又调用了异步函数，如果不考虑调用顺序且返回结果不会对后续
 * 调用产生影响，那与同步递归其实没多大区别。所以本文并不讨论与此相关的内容。
 * 本文要讨论的异步递归，需要考虑迭代的执行顺序。
 * 这里要实现一个现实的例子：
 * 输入一个路径，将路径中所有的目录以及文件按深度优先的顺序输出。
 * function listDir(path){
 *      fs.readdir(...,function(err,files){
 *          for(var i in files){
 *              if(isDirectory(files[i])){
 *                  output(files[i]);
 *                  listDir(files[i]);
 *              }else{
 *                  output(files[i]);
 *              }
 *          }
 *      });
 * }
 * 上面写了一段关于listDir伪实现代码，显然这代码是无法完成上述的要求。listDir中调用的
 * readdir是异步函数，所以listDir会直接返回。也就是for循环中files[i]还没执行完，就开始
 * 执行files[i+1],如果files[i+1]是文件的话极有可能比files[i]中的子文件或文件夹先输出。
 * 这里的递归应该有两个方向，一个是横向一个是径向。为了保证files[i+1]不在files[i]之前
 * 执行那不能使用循环，而应该使用递归。
 * function f(i){
 *      if(i>=files.length)
 *          return;
 *      if(isDirectory(files[i])){
 *          ...
 *          listDir(files[i]);
 *      }else{
 *          ...
 *      }
 *      f(i+1);
 * }
 * 上面的代码保证f(i+1)是在f(i)之后执行，但是如果files[i]为目录的情形下不能保证。
 * 如何才能保证呢？必须要等到files[i]输出所有的子文件夹和文件之后才能执行，files[i+1]
 * 是不是可以传个回调函数给listDir:
 * listDir((files[i],function ()
 *                  {f(i+1)}
 *              );
 * 这个函数体非常简单，这有短短的一个调用。那么这个回调函数在什么时候执行？这上面已经说
 * 明了，等files[i]的子目录和文件都输出之后。那什么时候算执行完？如果f函数返回那就算
 * 执行完毕了，所以回到函数应该在它返回之前执行。
 * if(i>=files.length){
 *      if(callback)
 *          callback();
 *      return;
 * }
 *
 */
var FS = require('fs');
var PATH = require('path');
var data = ['dongge','name',['zeus',['1','2'],'yun'],'user'];

function display(data){
    if(Array.isArray(data)){
        function print(i){
            if(i>=data.length){
                return
            }
            display(data[i]);
            print(i+1);
        }
        print(0);
    }else{
        console.log(data);
    }
}
function display_prefex(data,prefex){
    if(Array.isArray(data)){
        function print(i){
            if(i>=data.length){
                return
            }
            display_prefex(data[i],prefex+'**');
            print(i+1);
        }
        print(0);
    }else{
        console.log(prefex+data);
    }
}
/**
 * 递归显示路径下所有的目录和文件路径
 *
 * @param path
 * @param callback
 */
function listDir(path,callback){
    FS.readdir(path,function(err,files){
        if(err) throw err;
        function file(i){
            if(i>=files.length)
            {
                if(callback){
                    callback();
                }
                return;
            }
            var fileName = PATH.join(path,files[i]);
            FS.stat(fileName,function(err,stat){
                if(err) throw err;
                if(stat.isDirectory()){
                    console.log('+ '+fileName);
                    listDir(fileName,function(){
                        file(i+1);
                    });
                }else{
                    console.log('- '+fileName);
                    file(i+1);
                }

            })
        }
        file(0);
    })
}
/**
 * 此函数的难点在于如何按照深度优先的顺序输出
 * 由于fs.readdirs是异步函数，因此要想控制顺序输出
 * 所有操作务必放在回调函数中
 * fs.readdirs(...,function(err,files){
 *      for(var i in files){
 *          listDir(file[i]);
 *      }
 * })
 * 如果使用上面的代码对返回的文件递归调用listDir也是无法实现需求的
 * listDir不是同步的，由于在函数体中调用了文件处理的异步函数，它
 * 不会等到异步函数的回调函数执行完之后才返回，而是直接返回。那么上面的
 * 代码其实会立即进行下一步的迭代。显然这完全违背了初衷。我们应该在上一个
 * file处理完之后才处理下一个file。如果我们在上一个file处理函数的回调函数中
 * 调用listDir(files[i+1])那么就能实现这个目标。也就是说我们要将下面接着要做
 * 的工作放到马上要进行的作业的回调中，才能保证顺序执行。
 * 那我可不可以把传个回调函数给listDir，当它处理完当前任务之后就调用回调函数，也许
 * 这是好的想法。
 * 上面的for循环这代码肯定要改一改，如何改？
 * file(i){
 *      if(i>=files.length)
 *          return;
 *      ...
 *      file(i+1);
 * }
 * 这里定义了一个函数file，在这个函数中会自动调用下一个file(i+1)函数，这就实现了顺序
 * 调用的初步设想。
 * 现在这个函数目前其实什么都做不了，只是有个初步框架。
 * 这个函数的逻辑功能应该是对于文件应该就直接输出，如果是目录则应该调用listDir
 * file(i){
 *      if(i>=files.length)
 *          return;
 *      fs.stat(...,function (err,stat){
 *          ...
 *          if(stat.isDirectory){
 *              console.log(..files[i]);
 *              listDir(..files[i],function(){
 *                  file(i+1);
 *              })
 *          }else{
 *              console.log(..files[i]);
 *              file(i+1);
 *          }
 *      });
 *  }
 * 上面的逻辑中很清楚的实现了既定目标,file是文件的时候直接file(i+1)也就是说直接处理下一个。
 * 但是对于目录，先要处理完目录中的内容之后才能执行file(i+1)，所以这里要给listDir传递一个
 * 回调函数。
 * 那么问题来了，应该在什么地方调用回调函数？
 * 对于一个目录结构(+代表文件夹，-代表文件)
 * +aa
 *    +bb
 *      +cc
 *    +dd
 *      -2.txt
 *    -1.txt
 * 上面的执行路径是aa bb cc dd 2.txt 1.txt
 * 如果执行到bb也就是file(i)=bb file(i+1)=dd
 * 只有等到bb中直接子文件和目录都执行一遍之后才能执行dd
 * 也就是说在file()函数返回时执行，那file什么时候返回?
 * 那就是当i>=files.length之后,代码如下：
 * if(i>files.length){
 *      if(callback)
 *          callback();
 *      return;
 * }
 *
 */
listDir('../test');



